package org.example.myleet.p451;

import java.util.PriorityQueue;

public class Solution {

    static class F {
        int frequency;
        char c;

        public F(int frequency, char c) {
            this.frequency = frequency;
            this.c = c;
        }
    }

    public String frequencySort(String s) {
        int[] frequencies = new int[134];
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            ++frequencies[c];
        }
        PriorityQueue<F> pq = new PriorityQueue<>((o1, o2) -> {
            if (o2.frequency != o1.frequency) {
                return o2.frequency - o1.frequency;
            } else {
                return o1.c - o2.c;
            }
        });
        for (int i = 0; i < frequencies.length; ++i) {
            if (frequencies[i] > 0) {
                pq.offer(new F(frequencies[i], (char) i));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            F f = pq.poll();
            for (int i = 0; i < f.frequency; ++i) {
                sb.append(f.c);
            }
        }
        return sb.toString();
    }
}
